/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package com.lpcluster;

import com.lpcluster.LPCluster.CentroidType;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Class containing algorithm for K-Means clustering
 * @author edward
 */
public class KMeans {

	// Data points and clusters
	private List<WebPage> data;
	private List<Cluster> clusters;

	/**
	 * Factory method to initiate object with data points
	 * @param initData Data points for instantiation
	 * @return Instance
	 */
	static KMeans kMeansWithData(List<WebPage> initData) {
		KMeans kMeans = new KMeans();
		kMeans.data = initData;
		return kMeans;
	}
	
	/**
	 * Perform KMeans clustering on initData, and compute SSE
	 * @param nNumClusters Value of K
	 * @param type Centroid type
	 * @return SSE of resulting clusters
	 */
	double cluster(int nNumClusters, CentroidType type) {
		clusters = new ArrayList<Cluster>(nNumClusters);

		// Form initial centroids randomly
		List<WebPage> dataToProcess = new ArrayList<WebPage>(data);

		// ***** LP-LOC # 2 *****
		// Generate K initial clusters
		Random random = new Random(LPCluster.getSeed());
		for (int i = 0; i < nNumClusters; i++) {

			// Initialize new clusters
			Cluster newCluster = new Cluster();
			clusters.add(newCluster);

			// Assign random point to cluster and make it the centroid
			int nIndex = random.nextInt(dataToProcess.size());
			newCluster.addPoint(dataToProcess.get(nIndex));
			dataToProcess.remove(nIndex);
		}

		boolean changed;
		Double lastTotalSSE = null;
		double totalSSE = 0;
		do {
			
			// ***** LP-LOC # 3a *****
			// Assign all points to cluster with closest centroid
			for (WebPage point : data) {
				Cluster cluster = clusters.get(0);
				if (point == cluster.centroid()) continue;  // Skip centroid of cluster 0
				double nMinDistance = point.distanceWith(cluster.centroid());
				boolean centroidPoint = false;

				// ***** LP-LOC # 3b *****
				// Check other clusters to find one with centroid closest to this point				
				for (int i = 1; i < nNumClusters; i++) {
					Cluster compare = clusters.get(i);
					WebPage compareCentroid = compare.centroid();

					// Compute distance with current cluster centroid
					double nDistance;
					if (point == compareCentroid) {
						centroidPoint = true;
						break;  // Skip centroid points
					} 
					
					// Update minimum distance
					nDistance = point.distanceWith(compareCentroid);
					if (nDistance < nMinDistance) {
						nMinDistance = nDistance;
						cluster = compare;
					}
				}

				// Add point to closest cluster if not already done
				if (!centroidPoint) cluster.addPoint(point);
			}

			// Recompute centroids
			changed = false;
			totalSSE = 0;
			
			// ***** NO PERF (proper calculation of SSE) *****
			for (Cluster cluster : clusters) {
				if (type == CentroidType.Group) changed |= cluster.computeGroupCentroid();
				else if (type == CentroidType.Super) changed |= cluster.computeSuperCentroid();
				else if (type == CentroidType.Virtual) changed |= cluster.computeVirtualCentroid();
				totalSSE += cluster.computeSSE();
			}

			// Clean up clusters for recomputing
			if (changed) {
				
				// Group -> Report previous clustering if total SSE not improved
				if (type == CentroidType.Group) {
					if (lastTotalSSE!=null && lastTotalSSE<=totalSSE) return lastTotalSSE;
					lastTotalSSE = totalSSE;
				}
				
				// ***** LP-LOC # 8b *****
				for (Cluster cluster : clusters) cluster.removeAllExceptCentroid();
			}
		} while (changed);

		return totalSSE;
	}
}
